package demon1;

import java.util.Stack;

public class lianxi {
    public boolean isValid(String s) {
        Stack<Character> stack =new Stack<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='['){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    return false;
                }else{
                    char chL=stack.peek();
                    if(chL=='('&&ch==')'||chL=='{'&&ch=='}'||chL=='['&&ch==']'){
                        stack.pop();
                    }else{
                        return false;
                    }
                }
            }
        }
        return stack.empty();

    }



//    输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
//    假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
//    序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
//            1. 0<=pushV.length == popV.length <=1000
//            2. -1000<=pushV[i]<=1000
//            3. pushV 的所有数字均不相同
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        int j=0;
        Stack<Integer> stack=new Stack();
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while(!stack.empty()&&j<popV.length && stack.peek()==popV[j]){
                j++;
                stack.pop();
            }
        }
        return stack.empty();
    }



    //最小栈
    Stack<Integer> stack=new Stack<>();
    Stack<Integer>minstack=new Stack();
    public void push(int val) {
        stack.push(val);
        if(minstack.empty()){
            minstack.push(val);
        }else{
            if(minstack.peek()<=val){
                minstack.push(val);
            }
        }
    }

    public void pop() {
        if(stack.empty()){
            return;
        }
        int a=stack.peek();
        if(stack.pop()==minstack.peek()){
            minstack.pop();
        }
    }

    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }

    public int getMin() {
        if(minstack.empty()){
            return-1;
        }
        return minstack.peek();
    }



    //复写零
    public void duplicateZeros(int[] arr) {
        int cur=0;
        int dest=-1;
        //找位置
        while (cur<arr.length){
            if(arr[cur]==0){
                dest+=2;
            }else{
                dest++;
            }
            if(cur>=arr.length){
                break;
            }
            cur++;
        }
        //处理边界情况
        if(dest==arr.length){
            arr[arr.length-1]=0;
            dest-=2;
            cur--;
        }
        //开始复写,从后往前复写
        while(cur>=0){
            if(arr[cur]!=0){
                arr[dest]=arr[cur];
                cur--;
                dest--;
            }else{
                cur--;
                arr[dest]=0;
                dest--;
                arr[dest]=0;
                dest--;
            }
        }
    }
}
